package sortedList

import (
	"fmt"
)

type LinkedNode struct {
	Val  int
	Next *LinkedNode
}

type List struct {
	Head *LinkedNode
	Len  int
}

func New() *List {
	return &List{
		Head: nil,
		Len:  0,
	}
}

func (list *List) IsEmpty() bool {
	if list.Head == nil {
		return true
	}
	return false
}

//按序添加，普通单链表不能使用二分查找
func (list *List) Insert(value int) {
	list.Head = &LinkedNode{Next: list.Head} // 代理节点,临时节点,简化操作引入的
	var head *LinkedNode
	//1.在中间插入（包括头部插入）；头部插入也被添加代理头节点包含在中间插入的情况中了
	for head = list.Head; head.Next != nil; head = head.Next {
		if head.Next.Val >= value {
			head.Next = &LinkedNode{
				Val:  value,
				Next: head.Next,
			}
			list.Len++
			break
		}
	}
	//2. 在结尾插入
	if head.Next == nil {
		head.Next = &LinkedNode{
			Val:  value,
			Next: head.Next,
		}
		list.Len++
	}
	list.Head = list.Head.Next
}

func (list *List) PrintAll() {
	fmt.Printf("List.Len: %d \r\n", list.Len)
	var head *LinkedNode
	head = list.Head
	if head == nil {
		fmt.Println("list is empty")
		return
	}
	for ; head.Next != nil; head = head.Next {
		fmt.Printf("Val: %d -->", head.Val)
	}
	fmt.Printf("End: %d \r\n", head.Val)
}

func (list *List) Delete(value int) {
	//如果要删除第一个元素，和插入第一个元素一样，需要有个虚拟的前指针指向这个头。
	list.Head = &LinkedNode{Next: list.Head}
	for head := list.Head; head.Next != nil; head = head.Next {
		if head.Next.Val == value {
			//删除找到的这个元素
			head.Next = head.Next.Next
			list.Len--
		}
	}
	list.Head = list.Head.Next
}

func (list *List) PopFront() int {
	res := list.Head.Val //临时节点
	list.Head = list.Head.Next
	list.Len--
	return res
}
